package src.model.gameWorld.pathfinding.astar;

import java.util.*;

import src.model.gameObject.GameObject;
import src.model.gameObject.GameObjectSubtype;
import src.model.gameObject.GameObjectType;
import src.model.gameObject.ability.Passable;
import src.model.gameWorld.ActualMap;
import src.model.gameWorld.MapTileConfiguration;
import src.model.gameWorld.MovementValidator;
import src.model.gameWorld.Position;
import src.model.gameWorld.pathfinding.Path;
import src.model.gameWorld.pathfinding.PathfindingMap;
import src.model.gameWorld.pathfinding.astar.heuristic.PathfindingHeuristic;
import src.model.gameWorld.pathfinding.astar.heuristic.StraightLinePathfindingHeuristic;
import src.model.gameWorld.pathfinding.movement.DoubleMovementCost;
import src.model.gameWorld.pathfinding.movement.Movement;
import src.model.gameWorld.pathfinding.movement.MovementCost;

/**
 * <b>Overview</b>
 * The Pathfinder generates a Path, or a series of locations that must be moved to in order, from one place to another.
 *
 * <b>Responsibilities</b>
 * Generate a series of positions that lead from an initial position to a destnation position using the A Star algorithm.
 *
 * <b>Collaborators</b>
 * Position - Subcontractor: Positions handle the actual coordinates of each location on the map.
 * Path - Subcontractor: Paths represent the sequence of positions that form the solution to movement.
 *
 * <b>Implementor</b> - Bruce
 * <b>Tester</b> - Tim
 *
 * @author Bruce
 */
public final class AStarPathfinder
{
	private static AStarPathfinder pathfinder;

	private static PathfindingMap map;

	private static Movement move;

	/**
	 * @param mover the GameObject performing the move.
	 * @param destination the destination position.
	 * @return the Path between the mover and the destination tile using the current pathfinder.
	 */
	public static Path makePath(GameObject mover, Position destination)
	{
		if(pathfinder == null)
			pathfinder = new AStarPathfinder(map, move);
		return pathfinder.getPath(mover, destination);
	}

	/**
	 * Sets a map for future pathfinding calculations.
	 *
	 * @param pmap the map to use for pathfinding.
	 */
	public static void setMap(PathfindingMap pmap)
	{
		map = pmap;
	}

	/**
	 * Sets a movement cost calculator for future pathfinding calculations.
	 *
	 * @param mover the movement cost calculator to use for pathfinding.
	 */
	public static void setMover(Movement mover)
	{
		move = mover;
	}

	/**
	 * The PathfindingMap to pathfind over.
	 */
	private PathfindingMap pathfindingMap;

	/**
	 * The movement ability considered for this Pathfinder.
	 */
	private Movement movement;

	/**
	 * The heuristic used to determine H costs.
	 */
	private PathfindingHeuristic heuristic;

	/**
	 * Creates a new AStarPathfinder.
	 *
	 * @param pathfindingMap the PathfindingMap to pathfind over.
	 * @param movement the Movement to use for cost calculations.
	 * @param heuristic the PathfindingHeuristic to use for distance estimation.
	 * @throws NullPointerException if any argument is <code>null</code>.
	 */
	public AStarPathfinder(PathfindingMap pathfindingMap, Movement movement, PathfindingHeuristic heuristic) throws NullPointerException
	{
		if(pathfindingMap == null || movement == null || heuristic == null)
			throw new NullPointerException();

		this.pathfindingMap = pathfindingMap;
		this.movement = movement;
		this.heuristic = heuristic;
	}

	/**
	 * Creates a new AStarPathfinder using the StraightLine heuristic.
	 *
	 * @param pathfindingMap the Pathfinding map to use.
	 * @param movement the movement validator.
	 * @throws NullPointerException if either parameter is null.
	 */
	public AStarPathfinder(PathfindingMap pathfindingMap, Movement movement) throws NullPointerException
	{
		if(pathfindingMap == null || movement == null)
			throw new NullPointerException();

		this.pathfindingMap = pathfindingMap;
		this.movement = movement;
		this.heuristic = new StraightLinePathfindingHeuristic(pathfindingMap, movement);
	}

	/* (non-Javadoc)
	 * @see pathfindingMap.pathfinding.Pathfinder#getPath(pathfindingMap.Location, pathfindingMap.Location)
	 */
	public Path getPath(GameObject mover, Position destination)
	{
		Position start = map.findObject(mover);
		List<Node> open = new ArrayList<Node>();
		List<Node> closed = new ArrayList<Node>();

		open.add(new Node(null, start, new DoubleMovementCost(0.0), new DoubleMovementCost(0.0)));

		while(!open.isEmpty())
		{
			Node currentNode = first(open);
			Position currentLocation = currentNode.getLocation();
			open.remove(currentNode);
			closed.add(currentNode);
			if(currentLocation.equals(destination))
				return currentNode.getPath();

			for(Position nextLocation : pathfindingMap.adjacentPositions(currentLocation))
			{
				if(movement.validate(mover, nextLocation))
				{
					Node nextNode;
					try {
					nextNode = new Node(currentNode, nextLocation, movement.getMovementCost(mover, pathfindingMap.getDirectionTo(currentLocation, nextLocation), nextLocation), heuristic.getHeuristicCost(mover, nextLocation, destination));
					}catch(Exception e) {nextNode = new Node(currentNode, nextLocation, new DoubleMovementCost(0.0), heuristic.getHeuristicCost(mover, nextLocation, destination));}

					if(!closed.contains(nextNode))
					{
						ArrayList<Node> a = new ArrayList<Node>();
						a.addAll(open);
						if(a.contains(nextNode))
						{
							// Node already explored: check if this path is better and update
							open.clear();
							for(Node n : a)
							{
								if(nextNode.equals(n) && nextNode.compareTo(n) < 0)
								{
									n.updateGCost(currentNode, movement.getMovementCost(mover, pathfindingMap.getDirectionTo(currentLocation, nextLocation), nextLocation));
								}
								open.add(n);
							}
						}
						else
						{
							open.add(nextNode);
						}
					}
				}
			}
		}
		return null;
	}

	/**
	 * Returns the most attractive node from a list of open nodes.
	 *
	 * @param list the list of open nodes.
	 * @return the best node from the list.
	 */
	private Node first(List<Node> list)
	{
		Node min = list.get(0);
		for(Node n : list)
			if(n.compareTo(min) < 0)
				min = n;
		return min;
	}

	/**
	 * Represents a pathfinding node that contains all information required for A Star pathfinding.
	 *
	 * @author Catastrophe
	 */
	private class Node implements Comparable<Node>
	{
		/**
		 * The PathfindingLocation this Node represents.
		 */
		private Position pathfindingLocation;

		/**
		 * The F cost of moving to this Node.  F cost is the sum of G and H costs and is used to estimate how attractive movement to a PathfindingLocation is.
		 */
		private MovementCost fCost;

		/**
		 * The G cost of moving to this Node.  G cost is the total movement cost from the initial Node to this Node.
		 */
		private MovementCost gCost;

		/**
		 * The H cost of moving to this Node.  H cost represents an approximate cost of moving from a tile to the destination and is determined by a heuristic.
		 */
		private MovementCost hCost;

		/**
		 * This Node's parent Node.
		 */
		private Node parent;

		/**
		 * Creates a new Node.
		 *
		 * @param parent the new Node's parent node.
		 * @param pathfindingLocation the PathfindingLocation this Node represents.
		 * @param gCost the G cost of moving to this Node from the parent Node.
		 * @param hCost the H cost from this node to the destination.
		 * @throws NullPointerException if any argument except <i>parent</i> is <code>null</code>.
		 */
		public Node(Node parent, Position pathfindingLocation, MovementCost gCost, MovementCost hCost) throws NullPointerException
		{
			if(gCost == null || hCost == null || pathfindingLocation == null)
				throw new NullPointerException();
			this.pathfindingLocation = pathfindingLocation;
			this.hCost = hCost;
			updateGCost(parent, gCost);
		}

		/**
		 * @return the PathfindingLocation this Node represents.
		 */
		public Position getLocation()
		{
			return pathfindingLocation;
		}

		/**
		 * @return the F cost of moving to this Node.  F cost is the sum of G and H costs and is used to estimate how attractive movement to a PathfindingLocation is.
		 */
		public MovementCost getFCost()
		{
			return fCost;
		}

		/**
		 * @return the G cost of moving to this Node.  G cost is the total movement cost from the initial Node to this Node.
		 */
		public MovementCost getGCost()
		{
			return gCost;
		}

		/**
		 * @return the H cost of moving to this Node.  H cost represents an approximate cost of moving from a tile to the destination and is determined by a heuristic.
		 */
		public MovementCost getHCost()
		{
			return hCost;
		}

		/**
		 * Updates this Node with a better G cost and parent.
		 *
		 * @param parent this Node's new parent Node.
		 * @param gCost the G cost associated with moving from the parent Node to this Node.
		 */
		public void updateGCost(Node parent, MovementCost gCost)
		{
			this.parent = parent;
			this.gCost = gCost;
			if(parent != null)
				this.gCost.add(parent.getGCost());
			fCost = getGCost().clone();
			getFCost().add(hCost);
		}

		/**
		 * @return a Path that goes from the first Node in the chain to the last Node.
		 */
		public Path getPath()
		{
			List<Position> path = new ArrayList<Position>();
			addToPath(path);
			return new Path(path);
		}

		/**
		 * Recursively adds Locations to the specified list in reverse order so that the first Node in the chain is the first PathfindingLocation in the list.
		 *
		 * @param path the list to add to.
		 */
		private void addToPath(List<Position> path)
		{
			if(parent != null)
				parent.addToPath(path);
			path.add(getLocation());
		}

		/* (non-Javadoc)
		 * @see java.lang.Comparable#compareTo(java.lang.Object)
		 */
		public int compareTo(Node other)
		{
			return (int)(getFCost().getDoubleValue() - other.getFCost().getDoubleValue());
		}

		/**
		 * @param other the Node to check equivalence to.
		 * @return <code>true</code> if this Node is equivalent to the specified Node or <code>false</code> otherwise.
		 */
		public boolean equals(Node other)
		{
			return other == null ? false : pathfindingLocation.equals(other.pathfindingLocation);
		}

		/* (non-Javadoc)
		 * @see java.lang.Object#equals(java.lang.Object)
		 */
		@Override
		public boolean equals(Object other)
		{
			return other instanceof Node ? equals((Node)other) : false;
		}

		/* (non-Javadoc)
		 * @see java.lang.Object#hashCode()
		 */
		@Override
		public int hashCode()
		{
			return pathfindingLocation.hashCode() * 3 + 5;
		}

		/* (non-Javadoc)
		 * @see java.lang.Object#toString()
		 */
		@Override
		public String toString()
		{
			return "Node: " + getLocation();
		}
	}

	public static void main(String[] args)
	{
		ActualMap map = new ActualMap(5, 5, MapTileConfiguration.Octagonal);
		MovementValidator mv = new MovementValidator(map);

		GameObject mover = new GameObject(GameObjectType.UNIT, GameObjectSubtype.CORSAIR);
		GameObject passable = new GameObject(GameObjectType.TERRAIN, GameObjectSubtype.WATER);
		GameObject impassable = new GameObject(GameObjectType.TERRAIN, GameObjectSubtype.WATER);
		passable.addAbility(new Passable(passable, null));

		for(int y = 0; y < 5; ++y)
			for(int x = 0; x < 5; ++x)
				if(x == 3 && y == 2)
					map.placeObject(impassable, new Position(x, y));
				else
					map.placeObject(passable, new Position(x, y));

		AStarPathfinder.setMap(map);
		AStarPathfinder.setMover(mv);

		Position destination = new Position(4, 4);
		Position start = new Position(0, 1);

		map.placeObject(mover, start);

		long tm = System.currentTimeMillis();

		Path pt = AStarPathfinder.makePath(mover, destination);
		if(pt != null)
		for(Position p : pt)
			System.out.println(p);

		System.out.println(System.currentTimeMillis() - tm + " milliseconds");
	}
}